package 第四周;

/*
 * @author  YxinMiracle
 * @date  2022-04-29 7:52
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.*;

public class 最小基因变化 {

    public String[] genCharList = new String[]{"A", "C", "G", "T"}; // 基因中的字符
    public Set<String> genBankSet = new HashSet<>();
    public Map<String, Integer> resultMap = new HashMap<>(); // 记录广搜的层次

    /**
     * @param start 第一次的基因序列默认是合法的
     * @param end
     * @param bank
     * @return
     */
    public int minMutation(String start, String end, String[] bank) {
        for (int i = 0; i < bank.length; i++) genBankSet.add(bank[i]);
        if (!genBankSet.contains(end)){
            return -1;
        }

        // 创建队列
        Queue<String> genStringQueue = new LinkedList<>();
        genStringQueue.add(start);
        resultMap.put(start,0);
        while (!genStringQueue.isEmpty()) {
            // 当队列不为空时
            String pollString = genStringQueue.poll(); // 从队列中取出
            for (int i = 0; i < start.length(); i++) {
                for (int j = 0; j < genCharList.length; j++) {
                    if ((pollString.charAt(i)+"").equals(genCharList[j])) continue;
                    String nextString = changeStringByIndex(pollString, i, genCharList[j]);
                    if (genBankSet.contains(nextString)){
                        // 如果里面存在，即代表合法
                        resultMap.put(nextString,resultMap.get(pollString)+1);
                        if (nextString.equals(end)){
                            // 表示结束
                            return resultMap.get(nextString);
                        }else {
                            genStringQueue.add(nextString);
                        }
                    }
                }
            }
        }
        return -1;
    }

    public String changeStringByIndex(String s, int index, String wantReplaceChar) {
        StringBuilder sb = new StringBuilder(s);
        sb.replace(index, index + 1, wantReplaceChar);
        return sb.toString();
    }

//    public static void main(String[] args) {
//        String s = "aaa";
//        System.out.println(changeStringByIndex(s,1,"A"));
//    }

}
